Although digital circuits are typically constructed to accept data input—and provide data output—in a form that often appears to be analog or base ten, the circuits themselves operate in a binary domain. Thus, operations that appear relatively simple in base ten, often require many steps to be performed in binary. Although these steps are not complex in operation, they can easily grow to tens, hundreds, or thousands of individual steps that must be performed in order to implement the desired calculation. In a dedicated circuit, each of these individual steps requires a set of gates that must be fabricated in the integrated circuit.
As the term is used herein, “integrated circuit” includes devices such as those formed on monolithic semiconducting substrates, such as those formed of group IV materials like silicon or germanium, or group III-V compounds like gallium arsenide, or mixtures of such materials. The term includes all types of devices formed, such as memory and logic, and all designs of such devices, such as MOS and bipolar. The term also comprehends applications such as flat panel displays, solar cells, and charge coupled devices.
Thus, a good circuit design (in this context) is one that will generally reduce the number of gates that is required for a given calculation or reduce the number of stages of gates that is required for the calculation. This latter improvement is referred to as reducing the depth of the circuit, and it relates to the delay that is produced by the circuit. The greater the number of stages required by the circuit, the greater the circuit delay. Thus, good circuit designs not only require less space within the integrated circuit—because fewer gates are required—but also tend to produce results in a lesser period of time—because fewer stages are required (smaller depth). Thus, reducing at least one of the number of gates and the depth to perform a given calculation is highly desirable.
Examples of integrated circuits that tend to require a relatively large number of stages include adders, comparators, and counters of leading and trailing zeros and ones. When binary numbers having many digits are to be manipulated in this manner, a cascading series of gate circuits are typically employed. Circuit designs that reduce the depth of the circuit also tend to generally reduce the gate count of the circuit, thereby reducing the size of the circuit, the memory capacity required by the circuit, and the time required to implement the calculation.
FIG. 5 depicts a binary comparator for two binary numbers. Similarly, FIG. 6 depicts a binary adder for two binary numbers. In both cases, the critical path consists mostly of alternating AND and OR gates (this portion of the critical path is enclosed within the dashed box).
Many different methods have been devised to efficiently design such circuits under various constraints and with different optimization goals. For example, the “straightforward” method of a ripple carry adder produces a circuit that is extremely small in size, but with a depth of O(n), where n is the number of digits in the input binary numbers. Carry look-ahead adder, carry bypass adder, and carry select adder circuits contain more gates, but they are much faster. The best implementations have a depth of about 2 log2n. (Here and everywhere below, the depth is defined as the maximum number of two-input gates along paths from a circuit's inputs to its outputs, if the circuit cannot contain gates with more than two inputs). Khrapchenko developed a method in 1967 that produced circuits with a depth of log2n+const×√log2n, but his method was efficient only for huge values of n. Others have produced methods with a depth of not more than 1.441 log2n+const (in 2001) and 1.262 log2n+const (in 2003), both with very small constant additive terms. Thus, even seemingly-small improvements can be very important in reducing the space and time required by such a circuit.
What is needed, therefore, is a method that overcomes issues such as those described above, at least in part.